package com.leetcode.partition2;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/29 21:31
 */
public class LC130被围绕的区域 {

    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private static final int DUMMY = Integer.MAX_VALUE;       //虚拟根结点

    public static void solve(char[][] board) {
//        unionFind(board);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O' && (i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1)) {
                    dfs(board, i, j);
                }
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
        Arrays.stream(board).forEach(val -> System.out.println(Arrays.toString(val)));
    }

    public static void main(String[] args) {
        char[][] board = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'X', 'O', 'X'},
                {'X', 'O', 'O', 'X'},
        };
//        char[][] board = {
//                {'O', 'O', 'O'},
//                {'O', 'O', 'O'},
//                {'O', 'O', 'O'}
//        };
        solve(board);
    }

    private static void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#')
            return;
        board[i][j] = '#';      //已经走过的路径用#标注
        for (int[] dir : dirs) {
            dfs(board, i + dir[0], j + dir[1]);
        }
    }

    private static void unionFind(char[][] board) {
        int[] root = new int[board.length * board[0].length];
        //初始化，将二维数组映射到一维数组
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int index = i * board[0].length + j;
                if (i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1) {
                    //如果是边缘节点，就将当前节点接入到虚拟根节点中
                    root[index] = DUMMY;
                    continue;
                }
                root[index] = index;            //开始每个节点的根结点都和自己连通
            }
        }
        //遍历所有的区域，如果是边缘节点，都接入到rootNode上
        for (int i = 1; i < board.length - 1; i++) {
            for (int j = 1; j < board[0].length - 1; j++) {
                if (board[i][j] == 'X') continue;
                int index = i * board[0].length + j;
                for (int[] dir : dirs) {
                    int neighborRow = dir[0] + i, neighborCol = dir[1] + j;
                    //此时的节点不是边缘节点，需要上下右左的进行判断union
                    if (board[neighborRow][neighborCol] == 'O') {
                        int neighborIndex = neighborRow * board[0].length + neighborCol;
                        union(root, index, neighborIndex);
                    }
                }
            }
        }
        //通过find操作来判断当前节点的根结点是否是rootNode
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O' && find(root, i * board[0].length + j) != DUMMY) {
                    board[i][j] = 'X';
                }
            }
        }
        Arrays.stream(board).forEach(val -> System.out.println(Arrays.toString(val)));
    }

    private static int find(int[] root, int x) {
        if (x == DUMMY) return DUMMY;
        if (root[x] == x) return x;
        return find(root, root[x]);
    }

    private static void union(int[] root, int x, int y) {
        int rootX = find(root, x), rootY = find(root, y);
        if (rootX != rootY && rootX != DUMMY) root[rootX] = rootY;
    }
}
